package com.ls.que68_70;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ：ls
 * @description：主要是空格数目问题，整体不是很难
 * @date ：2021/11/26 19:48
 */
public class FullJustify {

    public static List<String> fullJustify(String[] words, int maxWidth){
        int i=0, j=0, total=0;
        List<String> res = new ArrayList<>();
        if (words.length == 1){
            String s = words[0];
            for (i=0; i< maxWidth - words[0].length(); i++)
                s += " ";
            res.add(s);
            return res;
        }

        while (j < words.length){
            total = 0;
            j = i;
            String s = "";
            while (j < words.length){
                total += words[j].length();
                if (total + j - i > maxWidth){
                    break;
                }
                j++;
            }
            // i 到 j-1 处为当前行的单词
            if (j == words.length){
                for (int k=i; k < j - 1; k ++){
                    s += words[k] + " ";
                }
                s += words[j-1];
                int remain = maxWidth - s.length();
                for (int k=0; k < remain; k++)
                    s += " ";
            }else{
                total -= words[j].length();
                // 总空格数量
                int space = maxWidth - total;

                // 间隔数
                int inter = j - i - 1;
                if (inter == 0){    // 代表此行只有一个单词
                    s += words[i];
                    for (int k=0; k< space; k++){
                        s += " ";
                    }
                }else{

                    // 最低空格数量
                    int low = space / inter;

                    // 更多空格的间隔
                    int more = space % inter;

                    // 更少空格的间隔
                    int less = inter - more;

                    for (int k=i; k < j - 1; k ++){
                        s += words[k];
                        if (k-i < more){
                            for (int t=0; t<low+1; t++){
                                s += " ";
                            }
                        }else{
                            for (int t=0; t<low; t++){
                                s += " ";
                            }
                        }
                    }
                    s += words[j-1];

                }
                i=j;
            }
            res.add(s);
        }

        return res;
    }

    public static void main(String[] args) {
        List<String> res = fullJustify(new String[]{"Science","is","what","we","understand","well","enough","to","explain",
                        "to","a","computer.","Art","is","everything","else","we","do"},20);
        for (String s : res){
            System.out.println(s);
        }
    }
}
